The present invention relates to methods and apparatus for embedding data in an image and recovering the embedded data therefrom.
Data hiding, also known as data concealing, is a process for embedding useful data (representing some information) into a cover media, such as image data. Cover media with data embedded therein is referred to herein as “marked media.” Data hiding may be employed for the purposes of identification, annotation, copyright protection, fingerprinting, and authentication. In such applications, the hidden data and the cover media may be closely related. This type of data embedding is often referred to as watermarking or more generally as “marking.” It is desirable for the hidden data to be perceptually transparent. Otherwise stated, the marked media should resemble the cover media as closely as possible.
The cover media will generally experience some distortion due to the presence of embedded data. Moreover, even after the embedded data are removed, it is generally difficult to restore the cover media to the condition it was in prior to embedding the data. Specifically, some permanent distortion of the cover media generally remains even after the hidden data have been extracted. The sources of distortion include round-off error, truncation error, and quantization error. This distortion presents a problem since for some applications such as medical diagnosis and law enforcement, it is important to accurately restore the cover media to the pre-embedding condition once the hidden data have been retrieved. The marking techniques satisfying this requirement are referred to as lossless or distortionless. Such marking techniques are also known as reversible marking techniques and are generally suitable for applications where the original media data should be accurately recovered.
Recently, some lossless marking techniques have been reported in the literature. The first method is carried out in the image spatial domain. See U.S. Pat. No. 6,278,791, issued Aug. 21, 2001, entitled “Lossless Recovery of an Original Image Containing Embedded Data,” by C. W. Honsinger, P. Jones, M. Rabbani, and J. C. Stoffel, (referred to herein as “Honsinger”), the disclosure of which is hereby incorporated herein by reference.
Another spatial domain technique was reported in Fridrich. J. Fridrich, M. Goljan and R. Du, “Invertible authentication,” Proc. SPIE, Security and Watermarking of Multimedia Contents, San Jose, Calif., January (2001) (referred to herein as “Fridrich”). The entire disclosure of this document is hereby incorporated herein by reference. There also exists a distortionless marking technique in the transform domain. B. Macq and F. Deweyand, “Trusted headers for medical images,” DFG VIII-D II Watermarking Workshop, Erlangen, Germany, October 1999 (referred to herein as “Macq”). The entire disclosure of this document is hereby incorporated herein by reference.
Based on our studies, transform domain methods can generally only embed about 2000 bits of data (equivalent to 250 bytes) in a 512×512×8 image. Hence, such methods will generally not work for applications where it is desired to embed much larger quantities of data. The capacity of the method reported in “De Vleeschouwer” is also very limited except that it exhibits robustness against high quality JPEG compression. C. De Vleeschouwer, J. F. Delaigle and B. Macq, “Circular interpretation on histogram for reversible watermarking,” IEEE International Multimedia Signal Processing Workshop, Cannes, France, pp. 345-350, October 2001 (referred to herein as “De Vleeschouwer”) The entire disclosure of this document is hereby incorporated herein by reference. These techniques are directed to authentication rather than to data hiding, and the total quantity of data embedded in the cover media is therefore limited.
The first lossless marking technique that is suitable for high embedding rate data hiding was presented in Goljan, M. Goljan, J. Fridrich, and R. Du, “Distortion-free data embedding,” Proceedings of 4th Information Hiding Workshop, Pittsburgh, Pa., April, 2001 (referred to herein as Goljan), the entire disclosure of which document is hereby incorporated herein by reference. In Goljan, the pixels in an image are divided into non-overlapped blocks, each block consisting of a number of adjacent pixels. For instance, this block could be a horizontal block having four consecutive pixels. A discrimination function is established to classify the blocks into three different categories: Regular, Singular, and Unusable. The authors used the discrimination function to capture the smoothness of the groups.
An invertible operation can be applied to groups. Specifically, the invertible operation can map a gray-level value to another gray-level value. This operation is invertible since applying it to a gray level value twice produces the original gray level value. This invertible operation is therefore called “flipping.” For typical images, flipping with a small amplitude will lead to an increase of the discrimination function, resulting in more regular groups and fewer singular groups. It is this bias that enables distortionless data hiding. While this approach hides data without distorting the cover data, the quantity of data which may be hidden employing this technique is still not large enough for certain applications. The payload was estimated to be in a range from 3,000 bits to 24,000 bits for a 512×512×8 gray image according to Goljan. Another problem with the method is that as the quantity of data embedded in the image increases, the visual quality of the image decreases. For instance, the PSNR (Peak Signal to Noise Ratio) may drop as low as 35 dB (decibels), and some undesired artifacts may appear in the image.
A method by Xuan, based on the integer wavelet transform, is a recently proposed reversible data hiding technique that can embed a large quantity of data. Guorong Xuan, Jidong Chen, Jiang Zhu, Yun Q. Shi, Zhicheng Ni, Wei Su, “Distortionless Data Hiding Based on Integer Wavelet Transform,” IEEE International Workshop on Multimedia Signal Processing, St. Thomas, US Virgin islands, December 2002 (referred to herein as “Xuan”). This document is hereby incorporated herein by reference. The main idea in Xuan is as follows. After the integer wavelet transform is applied to the original image, the bias between binary ones and binary zeroes in the bit-planes of the sub-bands LH, HL, and HH is significantly increased. Hence, the ones and zeroes and in these bit planes can be losslessly compressed to leave a lot of storage space for data embedding. After data embedding, an inverse integer wavelet transform is applied to form the marked image. The capacity achieved in this technique is quite large. The PSNR of the marked image is, however, not high due to the histogram modification applied in order to avoid overflow or underflow conditions. For some images, the PSNR is only 28 dB.
One method based on histogram manipulation is a recently disclosed lossless data hiding technique, which can embed a large amount of data (5 k-80 k bits for a 512×512×8 grayscale image) while preserving high visual quality (the PSNR is guaranteed to be above 48 dB) for a vast majority of images. Z. Ni, Y. Q. Shi, N. Ansari and W. Su, “Reversible data hiding,” IEEE International Symposium on Circuits and Systems, May 2003, Bangkok, Thailand, (referred to herein as “Ni”). This document is hereby incorporated herein by reference. This document (Ni) is not conceded to be prior art merely through its placement in the “Background of the Invention” section of this patent application.
However, only one prior lossless data hiding technique (Vleeschouwer) is robust against compression applied to the stego-image (the image including the embedded data). Specifically, only in Vleeschouwer can the hidden data still be extracted out correctly after the stego-media has gone through compression. With the other existing techniques, the embedded data cannot be recovered without error after stego-media compression.
While the De Vleeschouwer technique is robust to compression, it generates annoying salt-and-pepper noise because it uses modulo-256 addition. That is, when the pixel grayscale value is close to 256 (brightest) and/or 0 (darkest), the modulo-256 addition will likely cause flipping over between the brightest and darkest gray values. This often happens with medical images. One example is shown in FIG. 1, where FIG. 1A is an original medical image, and FIG. 1B is a stego-image. This type of salt-and-pepper noise is unacceptable for many applications. Therefore, there is a need in the art for a system and method for embedding an amount of robust data into cover media in a reversible manner (the original cover media can be preserved) without annoying salt-and-pepper noise.
In addition to hiding data, the embedding of data in cover media, such as images, can be employed for image authentication. Traditional digital signature techniques, such as DSA (Digital Signature Algorithm or RSA (Rivest, Shamir, Adleman) can provide effective and secure solutions for data authentication, which covers both data integrity protection and non-repudiation. Generally, modification of even a single bit will make the protected data inauthentic, which is advantageous since as every bit of data is vital. For example, if a transaction is made on-line, the exchanged data may contain information such as the amount of a payment, an account number, or payee's name. In this situation, a modification of even a single bit of such information will cause such a transaction to fail.
Directly applying the traditional digital signature techniques to image data can provide good protection of image data, but in an unreasonably strict way. Such authentication in image data is called “fragile authentication.” As images are exchanged between different entities within different media, the images unavoidably experience incidental distortion introduced by image transcoding, unreliable carrier actions, and multiple cycles of encoding and decoding. Although the incidental distortion changes image data, it doesn't change the meaning of the image from human's point of view. An image which has not been deliberately corrupted but which experiences incidental distortion will be considered unauthentic when employing the traditional digital-signature-based authentication scheme. Therefore, the fragility of traditional digital-signature techniques limits their application to image data. Accordingly, there is a need in the art for a system and method for embedding authentication data within cover media, such as images, which preserves a status of authenticity of the embedded data in the face of incidental distortion of the cover media.